package leetCode.solution;

import java.util.Arrays;
import java.util.Comparator;

public class RussianDollEnvelopes_354 {
	
	public static void main(String[] args) {
		int[][] arr = new int[][] {{4,5},{4,6},{6,7},{2,3},{1,1}};
		System.out.println(new RussianDollEnvelopes_354().maxEnvelopes(arr));
	}
	public int maxEnvelopes(int[][] envelopes) {
		if(envelopes==null || envelopes.length==0 || envelopes[0].length==0) {
			return 0;
		}
		
		Arrays.sort(envelopes, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1!=o2?o1[0]-o2[0]:o2[1]-o1[1];
			}
		});
		int widthArr[] = new int[envelopes.length];
		for(int i = 0;i<envelopes.length;i++) {
			widthArr[i]=envelopes[i][1];
		}
		return lengthOfLIS(widthArr);
	}
	
	public int lengthOfLIS(int[] nums) {
		if(nums==null || nums.length==0) {
			return 0;
		}
		int n = nums.length;
		int ends[] = new int[n]; // ends[i]:目前所有长度为i+1的递增子序列的最小结尾代表
		int right = 0;
		int maxLength = 1;
		ends[0]=nums[0];
		for(int i=0;i<n;i++) {
			int l = 0;
			int r = right;
			
			// l...r 范围找到>=nums[i]的最左侧位置
			while(l<=r) {
				int m = l+(r-l>>1);
				if(nums[i]>ends[m]) {
					l = m+1;
				}else {
					r = m-1;
				}
			}
			right = Math.max(right, l);
			ends[l] = nums[i];
			maxLength = Math.max(maxLength, l+1);
		}
		return maxLength;
	}
	public int maxEnvelopes1(int[][] envelopes) {
		if(envelopes==null || envelopes.length==0 || envelopes[0].length==0) {
			return 0;
		}
		
		Arrays.sort(envelopes, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1!=o2?o1[0]-o2[0]:o2[1]-o1[1];
			}
		});
		return lengthOfLIS1(envelopes);
	}
	
	public int lengthOfLIS1(int[][] nums) {
		if(nums==null || nums.length==0) {
			return 0;
		}
		int n = nums.length;
		int ends[] = new int[n]; // ends[i]:目前所有长度为i+1的递增子序列的最小结尾代表
		int right = 0;
		int maxLength = 1;
		ends[0]=nums[0][1];
		for(int i=0;i<n;i++) {
			int l = 0;
			int r = right;
			
			// l...r 范围找到>=nums[i]的最左侧位置
			while(l<=r) {
				int m = l+(r-l>>1);
				if(nums[i][1]>ends[m]) {
					l = m+1;
				}else {
					r = m-1;
				}
			}
			right = Math.max(right, l);
			ends[l] = nums[i][1];
			maxLength = Math.max(maxLength, l+1);
		}
		return maxLength;
	}
}
